package com.fjl.array.leetcode424;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/3/21 16:12
 */
/*
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。
示例 1：
    输入：s = "ABAB", k = 2
    输出：4
    解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
    输入：s = "AABABBA", k = 1
    输出：4
    解释：
    将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
    子串 "BBBB" 有最长重复字母, 答案为 4。
    可能存在其他的方法来得到同样的结果。
1、什么时候应该扩大窗口？
2、什么时候应该缩小窗口？
3、什么时候得到一个合法的答案？
针对本题，以上三个问题的答案是：
1、right - left - windowMaxCount <= k 时，所有进入窗口的字符都可以被替换成出现次数最多的字符 x，使得窗口内的所有元素都是重复的。
2、当 right - left - windowMaxCount > k 时，必须缩小窗口。因为此时窗口已经不合法，用尽 k 次替换机会也会有一个字符无法替换成 x。
3、只要可替换次数 k 大于等于 0，窗口中的字符串都可以全部替换成相同的，我们想求的是一个最大窗口长度。
 */
public class Clazz {
    public int characterReplacement(String s, int k) {
        int left = 0, right = 0;
        // 统计窗口中每个字符的出现次数
        int[] windowCharCount = new int[26];
        // 记录窗口中字符的最多重复次数
        // 记录这个值的意义在于，最划算的替换方法肯定是把其他字符替换成出现次数最多的那个字符
        int windowMaxCount = 0;
        // 记录结果长度
        int res = 0;
        while (right < s.length()) {
            // 扩大窗口
            int c = s.charAt(right) - 'A';
            windowCharCount[c]++;
            windowMaxCount = Math.max(windowMaxCount, windowCharCount[c]);
            right++;
            // 这个 while 换成 if 也可以
            while (right - left - windowMaxCount > k) {
                windowCharCount[s.charAt(left) - 'A']--;
                left++;
            }
            // 经过收缩后，此时一定是一个合法的窗口
            res = Math.max(res, right - left);
        }
        return res;
    }
}
